/*
 * ============================================================================
 * 队列 (Queue) - C++ 实现（模板版）
 * ============================================================================
 * FIFO 结构：入队/出队/取队头均 O(1)。
 */

#include <iostream>
#include <vector>
#include <stdexcept>
#include <string>

// 循环队列（数组实现）
template <typename T>
class CircularQueue {
public:
    explicit CircularQueue(size_t cap = 8)
        : _buf(cap), _head(0), _tail(0), _count(0) {}

    bool empty() const { return _count == 0; }
    bool full() const { return _count == _buf.size(); }
    size_t size() const { return _count; }

    void enqueue(const T& v) {
        if (full()) resize(_buf.size() * 2);
        _buf[_tail] = v;
        _tail = (_tail + 1) % _buf.size();
        ++_count;
    }

    T dequeue() {
        if (empty()) throw std::runtime_error("empty");
        T v = _buf[_head];
        _head = (_head + 1) % _buf.size();
        --_count; return v;
    }

    const T& front() const { if (empty()) throw std::runtime_error("empty"); return _buf[_head]; }

    void print() const {
        std::cout << "队头 → [";
        size_t idx = _head;
        for (size_t i = 0; i < _count; ++i) {
            std::cout << _buf[idx];
            if (i + 1 < _count) std::cout << ", ";
            idx = (idx + 1) % _buf.size();
        }
        std::cout << "] ← 队尾\n";
    }

private:
    void resize(size_t new_cap) {
        std::vector<T> nb(new_cap);
        for (size_t i = 0; i < _count; ++i) nb[i] = _buf[(_head + i) % _buf.size()];
        _buf.swap(nb); _head = 0; _tail = _count % _buf.size();
    }

    std::vector<T> _buf; size_t _head, _tail, _count;
};

// 链表队列
template <typename T>
struct QNode { T data; QNode* next; explicit QNode(const T& v):data(v),next(nullptr){} };

template <typename T>
class LinkedQueue {
public:
    LinkedQueue():_front(nullptr),_rear(nullptr),_count(0){}
    ~LinkedQueue(){ while(_front){ auto*t=_front; _front=_front->next; delete t; } }
    void enqueue(const T& v){ auto*n=new QNode<T>(v); if(!_rear){ _front=_rear=n; } else { _rear->next=n; _rear=n; } ++_count; }
    T dequeue(){ if(!_front) throw std::runtime_error("empty"); auto*t=_front; T v=t->data; _front=_front->next; if(!_front) _rear=nullptr; delete t; --_count; return v; }
    const T& front() const { if(!_front) throw std::runtime_error("empty"); return _front->data; }
    bool empty() const { return _front==nullptr; }
    size_t size() const { return _count; }
private:
    QNode<T>* _front; QNode<T>* _rear; size_t _count;
};

// 应用场景1：打印任务队列
void example_print_queue(){
    std::cout << "\n=== 应用场景1: 打印任务队列 ===\n";
    CircularQueue<std::string> q(4);
    q.enqueue("report.pdf"); q.enqueue("invoice.pdf"); q.enqueue("manual.pdf");
    q.print();
    while(!q.empty()) { std::cout << "打印: " << q.dequeue() << "\n"; }
}

// 应用场景2：BFS（简化示意）
void example_bfs(){
    std::cout << "\n=== 应用场景2: 广度优先搜索(BFS) ===\n";
    // 简化树: 1 -> 2,3 ; 2 -> 4,5
    LinkedQueue<int> q; q.enqueue(1);
    std::cout << "层序访问: 1, 2, 3, 4, 5\n";
    // 这里不构建完整图结构，演示队列在BFS中的作用
}

// 应用场景3：进程调度（时间片轮转）
struct Process { int pid; const char* name; int burst; };
void example_rr(){
    std::cout << "\n=== 应用场景3: 时间片轮转调度 ===\n";
    Process ps[3]={{1,"Browser",10},{2,"Editor",8},{3,"Player",12}};
    CircularQueue<int> ready(4); for(int i=0;i<3;++i) ready.enqueue(i);
    int time=0; while(!ready.empty()){
        int idx=ready.dequeue(); int exec= ps[idx].burst>3?3:ps[idx].burst;
        std::cout << "时间"<<time<<": 执行 "<<ps[idx].name<<" ("<<exec<<"ms)\n";
        time+=exec; ps[idx].burst-=exec; if(ps[idx].burst>0) ready.enqueue(idx);
    }
}

int main(){
    std::cout << "╔════════════════════════════════════════╗\n";
    std::cout << "║   队列 (Queue) - C++ 实现              ║\n";
    std::cout << "╚════════════════════════════════════════╝\n";

    std::cout << "\n--- 循环队列 ---\n";
    CircularQueue<int> cq; cq.enqueue(10); cq.enqueue(20); cq.enqueue(30); cq.print();
    std::cout << "出队: " << cq.dequeue() << "\n"; cq.print();
    cq.enqueue(40); cq.enqueue(50); cq.print();

    std::cout << "\n--- 链表队列 ---\n";
    LinkedQueue<int> lq; lq.enqueue(100); lq.enqueue(200); std::cout << "队头: " << lq.front() << ", 出队: " << lq.dequeue() << ", 剩余: " << lq.size() << "\n";

    example_print_queue();
    example_bfs();
    example_rr();

    std::cout << "\n✅ 优势: O(1)入队/出队, FIFO公平\n";
    std::cout << "⚠️ 局限: 只能访问队头/队尾, 搜索O(n)\n";
    return 0;
}
